package basic.study.leetcode;

/**
 * @ClassName Easy53
 * @Description 最大子序列和(dp，分治-线性树)
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/22 16:23
 * @Version 1.0
 */
public class Easy53 {
    /**
     * 动态规划
     */
    class Solution {
        public int maxSubArray(int[] nums) {
            if (nums.length == 1) {
                return nums[0];
            }
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
            }
            return dp[nums.length-1];
        }
    }
    /**
     * 分治
     */
    class Solution1 {
        public int maxSubArray(int[] nums) {
            return helper(nums, 0, nums.length-1);
        }

        private int helper(int[] nums, int left, int right) {
            if (left == right) return nums[left];

            int p = left + ((right - left)>>1);

            int leftSum = helper(nums, left, p);
            int rightSum = helper(nums, p+1, right);
            int crossSum = crossSum(nums, left, right, p);

            return Math.max(crossSum, Math.max(leftSum, rightSum));
        }

        private int crossSum(int[] nums, int left, int right, int p) {
            if (left == right) return nums[left];

            int leftSum = Integer.MIN_VALUE;
            int curSum = 0;
            for (int i = p; i >= 0; i--) {
                curSum += nums[i];
                leftSum = Math.max(leftSum, curSum);
            }

            int rightSum = Integer.MIN_VALUE;
            curSum = 0;
            for (int i = p+1; i <= right; i++) {
                curSum += nums[i];
                rightSum = Math.max(rightSum, curSum);
            }

            return leftSum + rightSum;
        }
    }
}
